package dtm;

import org.junit.jupiter.api.Test;
import tm.EnumDirection;
import tm.TMConfiguration;
import tm.TMRule;
import tm.Tape;
import java.util.Arrays;
import java.util.List;
import java.util.Set;

import static org.junit.jupiter.api.Assertions.assertEquals;

/**
 * @author haoly
 * @title TMWithInteralStorageTest
 * @date 2025/4/23 18:57
 * @description 标准DTM拓展--带内部存储的图灵机
 * ----------------------------------------------
 * 证明：标准的 DTM 结构（有限状态控制和无限纸带）足以模拟带有内部存储功能的图灵机。
 * 内部存储的能力是通过增加状态的数量并将信息“打包”进状态的定义中来实现的。
 * ----------------------------------------------
 * 假设我们想要一台图灵机来完成以下任务：
 * 读取纸带上字符串的第一个字符，然后将纸带头移动到字符串的末尾，并将之前读取的那个字符复制到末尾的空白位置。
 *
 * 对于一个带有寄存器的图灵机，这个过程可能就像这样：
 * 1. 读取纸带头的第一个字符。
 * 2. 将这个字符存储到一个寄存器里。
 * 3. 向右移动纸带头，直到找到字符串的末尾（比如遇到空白符）。
 * 4. 从寄存器中读取之前存储的字符。
 * 5. 在当前（末尾）位置写入这个字符。
 * 6. 停止。
 *
 * 而标准的 DTM 没有硬件上的“寄存器”。它是通过其当前所处的状态来“记住”那个字符的。
 * 1. 起始状态 (State 1): 机器从状态 1 开始。这个状态的含义是“准备读取字符串的第一个字符并记住它”。
 *
 * 2. 读取并“记住”字符（通过状态转换）： 当纸带头位于第一个字符上方时，机器根据读取到的字符进行状态转换：
 * 如果读取到 'a'，机器转换到状态 2。状态 2 的含义是：“现在我正在向右扫描寻找字符串末尾，并且我记得第一个字符是 'a'”。
 * 如果读取到 'b'，机器转换到状态 3。状态 3 的含义是：“现在我正在向右扫描寻找字符串末尾，并且我记得第一个字符是 'b'”。
 * 如果读取到 'c'，机器转换到状态 4。状态 4 的含义是：“现在我正在向右扫描寻找字符串末尾，并且我记得第一个字符是 'c'”。
 *
 * 3. 向右扫描（不同状态执行相同基本任务）： 在状态 2、状态 3 或状态 4 中，机器执行的任务都是“向右移动纸带头，跳过字符串中间的字符，直到找到末尾的空白符 _”。
 * 虽然它们执行的是同一个高层任务（向右扫描），但它们属于不同的状态，这个状态的区别正是用来表示“寄存器”里存储的字符信息。
 *
 * 4. 在末尾写入（根据当前状态决定写入哪个字符）： 当机器在状态 2、状态 3 或状态 4 中读取到空白符 _ 时（表示到达了字符串末尾），
 * 它会根据当前所在的状态来决定写入哪个字符，然后进入结束状态（状态 5）。
 *
 * 如果在状态 2（记得 'a'）读到 _，规则规定写入 'a'，然后转到状态 5。
 * 如果在状态 3（记得 'b'）读到 _，规则规定写入 'b'，然后转到状态 5。
 * 如果在状态 4（记得 'c'）读到 _，规则规定写入 'c'，然后转到状态 5。
 *
 *
 */
public class TMWithInteralStorageTest {
    @Test
    public void testRun(){
        // 如何用标准的DTM来模拟拓展了内部存储的TM？
        // 示例：将字符串的开头字符赋值到它的末尾
        List<TMRule<Integer>> rules = Arrays.asList(
                // state 1: 从磁带上读取第1个字符，记住该字符是'a'
                new TMRule<>(1, 'a', 2, 'a', EnumDirection.RIGHT),
                // state 1: 从磁带上读取第1个字符，记住该字符是'b'
                new TMRule<>(1, 'b', 3, 'b', EnumDirection.RIGHT),
                // state 1: 从磁带上读取第1个字符，记住该字符是'c'
                new TMRule<>(1, 'c', 4, 'c', EnumDirection.RIGHT),
                // state 2: 向右扫描来寻找字符串的末尾，且记住刚才读取的字符是'a'，并跳过'a'
                new TMRule<>(2, 'a', 2, 'a', EnumDirection.RIGHT),
                // state 2: 向右扫描来寻找字符串的末尾，且记住刚才读取的字符是'a'，并跳过'b'
                new TMRule<>(2, 'b', 2, 'b', EnumDirection.RIGHT),
                // state 2: 向右扫描来寻找字符串的末尾，且记住刚才读取的字符是'a'，并跳过'c'
                new TMRule<>(2, 'c', 2, 'c', EnumDirection.RIGHT),
                // state 2: 找到字符串的末尾了，并写入字符'a'
                new TMRule<>(2, '_', 5, 'a', EnumDirection.RIGHT),
                // state 3: 向右扫描来寻找字符串的末尾，且记住刚才读取的字符是'b'，并跳过'a'
                new TMRule<>(3, 'a', 3, 'a', EnumDirection.RIGHT),
                // state 3: 向右扫描来寻找字符串的末尾，且记住刚才读取的字符是'b'，并跳过'b'
                new TMRule<>(3, 'b', 3, 'b', EnumDirection.RIGHT),
                // state 3: 向右扫描来寻找字符串的末尾，且记住刚才读取的字符是'b'，并跳过'c'
                new TMRule<>(3, 'c', 3, 'c', EnumDirection.RIGHT),
                // state 3: 找到字符串的末尾了，并写入字符'b'
                new TMRule<>(3, '_', 5, 'b', EnumDirection.RIGHT),
                // state 4: 向右扫描来寻找字符串的末尾，且记住刚才读取的字符是'c'，并跳过'a'
                new TMRule<>(4, 'a', 4, 'a', EnumDirection.RIGHT),
                // state 4: 向右扫描来寻找字符串的末尾，且记住刚才读取的字符是'c'，并跳过'b'
                new TMRule<>(4, 'b', 4, 'b', EnumDirection.RIGHT),
                // state 4: 向右扫描来寻找字符串的末尾，且记住刚才读取的字符是'c'，并跳过'c'
                new TMRule<>(4, 'c', 4, 'c', EnumDirection.RIGHT),
                // state 4: 找到字符串的末尾了，并写入字符'c'
                new TMRule<>(4, '_', 5, 'c', EnumDirection.RIGHT)
        );

        DTMRulebook<Integer> rulebook = new DTMRulebook<>(rules);

        char blankChar = '_';
        Tape tape = new Tape(List.of(), 'b', List.of('c','b','c','a'), blankChar);

        System.out.println(tape);
        TMConfiguration<Integer> configuration = new TMConfiguration<>(1, tape);

        DTM<Integer> dtm = new DTM<>(configuration, Set.of(5), rulebook);
        dtm.run();
        assertEquals(5, dtm.getCurrentConfiguration().getState());
        System.out.println(dtm.getCurrentConfiguration().getTape());

    }
}
